home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / unix / volume4 / egrep < prev    next >
Encoding:
Internet Message Format  |  1986-11-30  |  26.8 KB
  1. From: James A. Woods <genrad!decvax!decwrl!jaw@RIACS.ARPA>
  2. Subject: egrep - More Pep for Boyer-Moore Grep
  3. Newsgroups: mod.sources
  4. Approved: jpn@panda.UUCP
  5.  
  6. Mod.sources:  Volume 4, Issue 47
  7. Submitted by: James A. Woods <ames!jaw@RIACS.ARPA>
  8.  
  9.  
  10. as advertised in net.unix.  -- ames!jaw
  11.  
  12. ----------
  13. #! /bin/sh
  14. # This is a shell archive, meaning:
  15. # 1. Remove everything above the #! /bin/sh line.
  16. # 2. Save the resulting text in a file.
  17. # 3. Execute the file with /bin/sh (not csh) to create the files:
  18. #    pep4grep.1
  19. #    pep4grep.2
  20. #    Makefile
  21. #    egrep.c
  22. #    compat-sys5.c
  23. # This archive created: Wed Apr  2 18:19:14 1986
  24. export PATH; PATH=/bin:$PATH
  25. echo shar: extracting "'pep4grep.1'" '(6104 characters)'
  26. if test -f 'pep4grep.1'
  27. then
  28.     echo shar: will not over-write existing file "'pep4grep.1'"
  29. else
  30. cat << \SHAR_EOF > 'pep4grep.1'
  31. >From postnews Tue Mar 18 18:04:08 1986
  32. Subject: More Pep for Boyer-Moore Grep (part 1 of 2)
  33. Newsgroups: net.unix
  34.  
  35. #  The chief defect of Henry King
  36.    Was chewing little bits of string.
  37.  
  38.     -- Hilaire Belloc, Cautionary Tales [1907]
  39.  
  40. #  Attempt the end, and never stand to doubt
  41.    Nothing's so hard but search will find it out.
  42.  
  43.     -- Robert Herrick, Hesperides [1648]
  44.  
  45.      The world does not need another 'grep' variant.  And so, what is this
  46. we offer?  On the surface, the exact same 'egrep' actually, but underneath,
  47. a swift Boyer-Moore hybrid, in C, which can beat assembler versions utilizing
  48. microcoded string search instructions.  The offering, designed in the
  49. Kernighanian sense to utilize the existing 'egrep' when it must, also
  50. makes use of Mr. Henry Spencer's regexp(3) functions in an unusual way.
  51. For the edification of those without on-line access to system source code,
  52. the vendor-supplied 'egrep' is left in a pristine state.
  53.  
  54.      With code now wending its way to mod.sources, we obtain the following
  55. results.  Times (in seconds) are all measured on a VAX 11/750 system running
  56. BSD 4.2 on Fujitsu Eagles, although our 'egrep' has been run on the Sun 2,
  57. V7 Unix/PDP 11, Vaxen configured with System V, and, for added effect, the
  58. NASA Ames Cray 2.
  59.  
  60.             200K bytes       user   sys    notes
  61.  
  62.   (new) egrep  astrian /usr/dict/words     0.4    0.5    implementation by "jaw"
  63.     match      "           "         0.5    0.5    VAX-only (Waterloo)
  64.     bm      "           "         1.1    0.6    Peter Bain's version 2
  65.   (old) egrep     "           "      5.6    1.7    standard    
  66.  
  67. [note:  the output here is the single word "Zoroastrian".]
  68.  
  69.      Aha, you quip -- this is all very fine for the 99 and 44/100's percent
  70. metacharacter-free world, but what about timing for shorter strings, character
  71. folding, as well as for the more interesting universe of extended regular 
  72. expressions?  Samples forthwith.  (Egrep below refers to the new one, times for
  73. the /usr/bin code being about the same as above on most any pattern.)
  74.  
  75.     egrep      zurich        0.4  0.5    0 words output
  76.     egrep -i zuRich      0.4  0.5    1 
  77.     egrep -i zeus          0.6  0.6    1
  78.     egrep -i zen          0.7  0.6    11
  79.     bm      zen          2.2  0.6    10
  80.     egrep      ZZ          0.8  0.6    0
  81.     bm      ZZ          3.0  0.7    0
  82.     egrep -c Z          1.5  0.6    19
  83.     bm -c      Z          5.9  0.7    19
  84.  
  85. Admittedly, most people (or programs) don't search for single characters,
  86. where Boyer-Moore is a bit slow, but it's important for the layered regular
  87. expression approach described herein.  We might point out from the above that
  88. the popular "fold" option crippled by 'bm' costs little; it's only a slight
  89. adjustment of the precomputed "delta" table as well as a single character
  90. array reference in a secondary loop.  Why has Bain claimed complexity for this?
  91. Also, the times show that the inner loop chosen for our code (modeled after
  92. the original speedup done by Boyer-Moore for the PDP 10) consistently betters
  93. the "blindingly fast" version by a factor of two to three.  The tipoff was
  94. from previous paper studies (esp. Horspool, see header notes in code) noting
  95. that the algorithm should, when implemented efficiently, best typical microcode.
  96. Now it does. 
  97.  
  98.     while ( (k += delta0 ( *k )) < strend )
  99.         ;        /* over 80% of time spent here */
  100.  
  101. is the key (modulo precomputation tricks), and takes but three or four
  102. instructions on most machines.
  103.  
  104.      Basic method for regular expressions:
  105.  
  106.     (1) isolate the longest metacharacter-free pattern string via the
  107.         "regmust" field provided by H. Spencer's regcomp() routine.
  108.  
  109.         (Non-kosher, but worth not re-inventing the wheel.
  110.         v8 folks just might have to reverse-engineer Spencer's
  111.         reverse-engineering to provide equivalent functionality.
  112.         You see, there are many more sites running his code than v8.
  113.         Besides, we enjoy using regexpr technology on itself.
  114.  
  115.     (2) for "short" input, submatching lines are passed to regexec().
  116.  
  117.     (3) for "long" input, start up a standard 'egrep' process via
  118.         popen() or equivalent.  Why not just use regexec()?  Unfortunately
  119.         for our application, Spencer's otherwise admirable finite-state
  120.         automaton exhibits poor performance for complex expressions.
  121.         Setting a threshold on input length, though not perfect, helps.
  122.         If pipes on Unix were free, we'd use this way exclusively.
  123.         Until then, we buy happiness for those who might
  124.  
  125.             egrep stuff /usr/spool/news/net/unix/*
  126.  
  127.         or on other directories full of short files.
  128.  
  129. So,
  130.     newegrep -i 'hoe.*g'         words     1.2  1.1
  131.                          {shoestring,Shoenberg}
  132.     newegrep '(a|b).*zz.*[od]$' words     1.5  1.1
  133.                          {blizzard,buzzword,palazzo}
  134.     oldegrep                 6.3  1.4
  135. but,
  136.     {new,old}egrep -c '(first|second)'    similar times (no isolate)
  137.  
  138. Again, we stress that given the different nature of the simulations of the two
  139. nondeterministic reg. expr. state-machines (one functionless), cases can be
  140. "cooked" to show things in a bad light, so a hybrid is warranted.
  141. We can generally do better incorporating the Boyer-Moore algorithm directly
  142. into the AT&T code.  For the last example, the abstraction
  143.  
  144.     (egrep first words &; egrep second words) | sort -u | wc
  145.  
  146. ideally would work better on a parallel machine, but if you're expecting
  147. something as amazing in this draft as, say, Morwen B. Thistlethwaite's 52-move
  148. Rubik's Cube solution, you're in the wrong place.
  149.  
  150.      About options -- system V ones are supported (-c, -l, bonus -i for BSD);
  151. the 'egrep' here just hands off patterns to old code for things like -n, -b,
  152. -v, and multiple patterns.  As a bone to throw to the enemies of the cat-v
  153. school, there is a -h (halt after printing first match), but we don't talk
  154. about it much.  Multiple patterns can done ala 'bm' but laziness in the
  155. presence of lack of knowledge of where 'fgrep' wins has prevailed for version 1.
  156.  
  157.      Personally I feel that adapting ("internationalizing") the 'egrep' effort
  158. for two-byte Kanji is FAR more important than tweeking options or tradeoffs,
  159. so for you large-alphabet Boyer-Moore algorithm specialists, send ideas
  160. this way.
  161.      
  162.      Further historical/philosophical comments follow in the sequel.
  163.  
  164.      James A. Woods (ames!jaw)
  165.      NASA Ames Research Center
  166.  
  167. SHAR_EOF
  168. if test 6104 -ne "`wc -c < 'pep4grep.1'`"
  169. then
  170.     echo shar: error transmitting "'pep4grep.1'" '(should have been 6104 characters)'
  171. fi
  172. fi
  173. echo shar: extracting "'pep4grep.2'" '(4623 characters)'
  174. if test -f 'pep4grep.2'
  175. then
  176.     echo shar: will not over-write existing file "'pep4grep.2'"
  177. else
  178. cat << \SHAR_EOF > 'pep4grep.2'
  179. >From postnews Tue Mar 18 18:05:22 1986
  180. Subject: More Pep for Boyer-Moore Grep (part 2 of 2)
  181. Newsgroups: net.unix
  182.  
  183. #  "Gratiano speaks an infinite deal of nothing, more than any man in all
  184.    of Venice.  His reasons are as two grains of wheat hid in two bushels of
  185.    chaff:  you shall seek all day ere you find them, they are not worth
  186.    the search."  -- Shakespeare, Merchant of Venice
  187.  
  188. ... or, part 2, "Reach out and Boyer-Moore Egrep Someone"
  189.  
  190.      Maybe you never use 'grep'.  Then ignore this.  But if you do, why not
  191. use the best algorithm?  Serious addicts know that for unstructured yet
  192. stable text, B-trees are used for speed, or something like Lesk's nifty
  193. (and unavailable) 'grab' suite for inverted files are ways to go.  Barring file
  194. inversion daemons for netnews and other ephemera, we are limited to the
  195. present improvements.
  196.  
  197.      Proper skeptics should question why a nearly I/O-bound program
  198. (but not for any CPU with less than the power of a 780, alas) should be
  199. made more so.  The question was posed in B & M's classic 1978 CACM
  200. paper -- the answer then was to free up more CPU cycles for timesharing.
  201. Now, our motivations are more mundane (we won't have desktop 5 MIP machines
  202. for another year), but not only that, we've discovered that the Cray 2's
  203. standard 'egrep' is also very anemic, performing 8-12 times as worse as ours
  204. on simple patterns.  For shame, especially since hearing of the rumor that
  205. certain group theorists have a search application ready for testing.
  206. Boyer-Moore could fill in until a Cray vectorizing C compiler shows up.
  207. Sheer speed for machines whose filesystems are cached in memory is nice too.
  208.  
  209.      A quick-and-dirty rundown of the debts to which the new hybrid pays
  210. now follows.
  211.  
  212.     Thompson, K. T. (CACM, November 1968):
  213.         Regular Expression Search Algorithm.  As usual, obvious
  214.         once you understand it.  The current 'egrep'.  Still
  215.         useful as a base.  Abstracted by Aho/Ullman as Algorithm
  216.         9.1 in Design and Analysis of Computer Algorithms.
  217.  
  218.     Boyer/Moore:
  219.         Not quite pre-Unix.  Oh well.  Modern designers should
  220.         know better now, if they want their stuff to get out there.
  221.         By the way, I haven't used delta2 (or 1) since the O(mn) case
  222.         case doesn't come up too often.  Sure Knuth stood on his head
  223.         to better the linearity, but his proof had a bug in it until
  224.         the 1980 SIAM J. Comput. retraction.  Would you want to code
  225.         something that even Knuth trips up on?
  226.  
  227.          Now to assuage nagging feelings that geneticists might want
  228.         to search entire libraries of 9000-unit nucleotide protein
  229.         sequences for ((AGCA|TTGCA).*TGC)|AGCT)?T?A+ or some nonsense
  230.         which MIGHT be nonlinear, you would want delta2.  So convince
  231.         someone to do the Galil/Apostolico/Giancarlo 2n comparison
  232.         worst case stuff.  See egrep.c for reference.
  233.         
  234.     Gosper, W. (HAKMEM 1972):
  235.         Gosper didn't get around to the Thompson-like machine until
  236.         1972 with HAKMEM.  His PDP 10 code is nevertheless valiant.
  237.         He is also (barely) credited with conceiving the backwards
  238.         match idea independently.  Where is he now?
  239.         
  240.     Morris/Pratt:
  241.         Nice guys, but for this purpose, has-beens.
  242.         Neat to see a hacker's triumph bury some theory.
  243.  
  244.     Horspool (Software Practice & Experience, 1980):
  245.         Now here's a Canadian after the heart of things
  246.         (perfect hashing, text compression, NP-complete
  247.         code generation probs., etc.)  Did some Amdahl
  248.         timings to show that delta2 is not so hot.
  249.         Knows about Search For Least Frequent Character First,
  250.         which is useful for short patterns. 
  251.  
  252.     {,e,f}grep man page:
  253.         The laughable bugnote "but we do not know a single algorithm
  254.         that spans a wide enough range of space-time tradeoffs"
  255.         certainly presumes that there is no such thing as switching
  256.         logic.  How the 'grep' family got into a multiple-version
  257.         mess is probably a Guy Harris story; 'egrep' looks like the
  258.         winner, as its functionality is pretty much a superset of
  259.         the other two.  The K & P teaser (p. 105) offers hope for
  260.         unification, but we see no difference with extant V8 code.
  261.  
  262.      "Not cited in the text" -- the sexy randomized Karp/Rabin string searcher
  263. (Sedgewick, Algorithms, or Karp's Turing Award Lecture), and the ribald classic
  264. Time Warps, String Edits, and Macromolecules -- The Theory and Practice
  265. of Sequence Comparison (Kruskal & Sankoff).  Inquire within.
  266. Thanks for your patience,
  267.  
  268.      James A. Woods (ames!jaw)
  269.      NASA Ames Research Center
  270.  
  271. P.S.
  272.      Current applications for Boyer-Moore code include modification of 
  273. 'fastfind' for true speed, as well as substring search for 'grab', both
  274. benefiting from BM-style search thru incrementally-compressed files/indices.
  275.  
  276. SHAR_EOF
  277. if test 4623 -ne "`wc -c < 'pep4grep.2'`"
  278. then
  279.     echo shar: error transmitting "'pep4grep.2'" '(should have been 4623 characters)'
  280. fi
  281. fi
  282. echo shar: extracting "'Makefile'" '(593 characters)'
  283. if test -f 'Makefile'
  284. then
  285.     echo shar: will not over-write existing file "'Makefile'"
  286. else
  287. cat << \SHAR_EOF > 'Makefile'
  288. # optional items for ENV:
  289. # -DBSD            make -i work as in System V
  290. # -I.            use regexp.h in current directory, not /usr/include
  291. # -DEGREP=path        default /usr/bin/egrep
  292. # -DV7            invoke xread() for system time quirk
  293.  
  294. ENV= -I. -DBSD
  295.  
  296. # optional items for OBJ:
  297. # compat-sys5.o        for V7 or BSD 4.2 systems w/no getopt(3) or string(3)
  298. # regexp.o        if Henry Spencer's regexp(3) is not installed
  299. # regerror.o            "
  300. #            V8 people -- your regexp.h won't do
  301.  
  302. OBJ= regexp.o regerror.o compat-sys5.o
  303.  
  304. CFLAGS= -O -i $(ENV) 
  305.  
  306. egrep:    egrep.o $(OBJ)
  307.     cc $(CFLAGS) $(OBJ) egrep.o -o egrep
  308.  
  309. install:
  310.     mv egrep /usr/local
  311. SHAR_EOF
  312. if test 593 -ne "`wc -c < 'Makefile'`"
  313. then
  314.     echo shar: error transmitting "'Makefile'" '(should have been 593 characters)'
  315. fi
  316. fi
  317. echo shar: extracting "'egrep.c'" '(11219 characters)'
  318. if test -f 'egrep.c'
  319. then
  320.     echo shar: will not over-write existing file "'egrep.c'"
  321. else
  322. cat << \SHAR_EOF > 'egrep.c'
  323. /*
  324.      Boyer/Moore/Gosper-assisted 'egrep' search, with delta0 table as in
  325.      original paper (CACM, October, 1977).  No delta1 or delta2.  According to
  326.      experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of minimal
  327.      practical value.  However, to improve for worst case input, integrating
  328.      the improved Galil strategies (Apostolico/Giancarlo, Siam. J. Comput.,
  329.      February 1986) deserves consideration.
  330.  
  331.      Method:     extract longest metacharacter-free string from expression.
  332.         this is done using a side-effect from henry spencer's regcomp().
  333.         use boyer-moore to match such, then pass submatching lines
  334.         to rexexp() for short input, or standard 'egrep' for long
  335.         input.  (this tradeoff is due to the general slowness of the
  336.         regexp() nondeterministic machine on complex expressions,
  337.         as well as the startup time of 'egrep' on short files.)
  338.         alternatively, you may change the faster 'egrep' automaton
  339.         to include boyer-moore directly.
  340.      Future: 
  341.              beef up for multiple patterns ala bm/fgrep.  can do fast -n 
  342.         via file rescan, but it's a luxury.  adapt 'fastfind'.
  343.         internationalize for kanji.
  344.  
  345.      James A. Woods                    Copyright (c) 1986
  346.      NASA Ames Research Center
  347. */
  348. #ifdef    V7
  349. #define BSD
  350. #define void    int
  351. #endif
  352.  
  353. #include <stdio.h>
  354. #include <ctype.h>
  355. #include <sys/types.h>
  356. #include <sys/stat.h>
  357. #include <regexp.h>        /* must be henry spencer's version */
  358.  
  359. #ifdef    BSD
  360. #define    strchr    index
  361. #endif
  362. #ifndef EGREP
  363. #define    EGREP    "/usr/bin/egrep"  /* prevent installation-dependent recursion */
  364. #endif
  365. #define BUFSIZE    8192
  366. #define PATSIZE 1000
  367. #define LARGE     BUFSIZE + PATSIZE
  368. #define FSIZE    50000        /* algorithm tradeoff at this length (ad hoc) */
  369. #define NL    '\n'
  370. #define    EOS    '\0'
  371.  
  372. extern char *optarg;
  373. extern int optind;
  374.  
  375. int cflag, iflag, eflag, fflag, lflag;
  376. int boyflag, rxflag;
  377. int hflag;
  378. int nfile, nsuccess;
  379. long nmatch;
  380.  
  381. regexp *rspencer;
  382. char *pattern, *patboy;
  383. int delta0[256];        /* ascii only -- see note at gosper() */
  384. char cmap[256];            /* (un)folded characters */
  385. char str[BUFSIZE+2];
  386. char linetemp[BUFSIZE];
  387. char grepcmd[PATSIZE]; 
  388.  
  389. struct stat stbuf;
  390. int fd;
  391. FILE *egout, *mcilroy(), *popen();
  392. char *strchr(), *strcpy(), *strncpy(), *strpbrk(), *malloc();
  393. char *fold(), *sys5fold();
  394.  
  395. main ( argc, argv )
  396.     int argc; char *argv[];
  397. {
  398.         int c;
  399.         int errflag = 0;
  400.         int oldegrep = 0;
  401.  
  402.         while ( (c = getopt ( argc, argv, "bchie:f:lnv" ) ) != EOF )
  403.  
  404.                 switch(c) {
  405.  
  406.         case 'f':
  407.             fflag++;
  408.                 case 'b':
  409.         case 'n':
  410.         case 'v':
  411.             oldegrep++;    /* boyer-moore of little help here */
  412.                         continue;
  413.                 case 'c':
  414.                         cflag++;
  415.                         continue;
  416.                 case 'e':
  417.                         eflag++;
  418.                         pattern = optarg;
  419.                         continue;
  420.         case 'h':
  421.             hflag++;    /* shh ... for newshounds */
  422.             continue;
  423.                 case 'i':
  424.                         iflag++;
  425.                         continue;
  426.                 case 'l':
  427.                         lflag++;
  428.                         continue;
  429.                 case '?':
  430.                         errflag++;
  431.             }
  432.         argc -= optind;
  433.         if ( errflag || ((argc <= 0) && !fflag) )
  434.         oops ( "usage: egrep [-bcilnv] [-e exp] [-f file] [strings] [file]" );
  435.         if ( !eflag ) {
  436.                 pattern = argv[optind++];
  437.                 argc--;
  438.         }
  439.     if ( oldegrep || (strchr ( pattern, '\n' ) != NULL) ) {
  440.         execvp ( EGREP, argv );
  441.         oops ( "can't exec old 'egrep'" );
  442.     }
  443.         if ( iflag ) {
  444.         strcpy ( pattern, fold ( pattern ) );
  445.     }
  446.     if ( strpbrk ( pattern, "^$.[]()?+*|\\" ) == NULL ) {    /* do boyer-moore only */
  447.         boyflag++;
  448.         rxflag = 0;
  449.         patboy = pattern;
  450.     }
  451.     else {     
  452.         /*
  453.             first compile a fake regexp to isolate longest
  454.             metacharacter-free string
  455.         */
  456.         {
  457.             char *dummyp;
  458.             dummyp = malloc ( (unsigned) strlen ( pattern ) + 5 );
  459.             sprintf ( dummyp, "(.)*%s", pattern );
  460.             rspencer = regcomp ( dummyp );
  461.         }
  462.         if ( rspencer -> regmust == NULL ) {        /* pattern too complicated */
  463.             execvp ( EGREP, argv );
  464.             oops ( "can't exec old 'egrep'" );
  465.         }
  466.         patboy = rspencer -> regmust;
  467.         if ( (rspencer = regcomp ( pattern )) == NULL )
  468.             oops ( "egrep: regcomp failure" );
  469.     }
  470.     gosper ( patboy );
  471.         argv = &argv[optind];
  472.         nfile = argc;
  473.         if ( argc <= 0 ) {        /* process stdin */
  474.                 if ( lflag )
  475.             exit ( 1 );
  476.         fd = 0;
  477.         if ( !boyflag )
  478.             if ( (egout = mcilroy ( (char *) NULL )) == NULL )
  479.                 oops ( "egrep: no processes" );
  480.                 boyermoore ( (char *) NULL, patboy );
  481.         if ( !boyflag )
  482.             pclose ( egout );
  483.         }
  484.         else {
  485.                 while ( --argc >= 0 ) {
  486.                     if ( (fd = open ( *argv, 0 )) <= 0 ) {
  487.                             fprintf ( stderr, "egrep: can't open %s\n", *argv );
  488.                             nsuccess = 2;
  489.                 argv++;
  490.                 continue;
  491.             }
  492.             if ( !boyflag ) {
  493.                 fstat ( fd, &stbuf );
  494.                 if ( stbuf.st_size < FSIZE )
  495.                     rxflag = 1;
  496.                 else {
  497.                     rxflag = 0;
  498.                     if ( (egout = mcilroy ( *argv )) == NULL )
  499.                         oops ( "egrep: no processes" );
  500.                 }
  501.             }
  502.                         boyermoore ( *argv, patboy );
  503.             if ( !boyflag && !rxflag ) {
  504.                 fflush ( egout );
  505.                 pclose ( egout );
  506.             }
  507.             close ( fd );
  508.             argv++;
  509.                 }
  510.     }
  511.         exit ( (nsuccess == 2) ? 2 : (nsuccess == 0) );
  512. }
  513.  
  514. boyermoore ( file, pattern )    /* "reach out and boyer-moore search someone" */
  515.     char *file, *pattern;    /* -- soon-to-be-popular bumper sticker */
  516. {
  517.     register char *k, *strend, *s;
  518.     register int j;
  519.     int patlen;
  520.     char *t;
  521.     char *gotamatch();
  522.     int nleftover, count;
  523.  
  524.     patlen = strlen ( pattern );
  525.     nleftover = nmatch = 0;
  526.  
  527. #ifdef V7
  528. #define read xread
  529. #endif
  530.     while ( (count = read ( fd, str + nleftover, BUFSIZE - nleftover )) > 0 ) {
  531.  
  532. #undef read
  533.         count += nleftover;
  534.         if ( count != BUFSIZE && fd != 0)
  535.             str[count++] = NL;    /* insurance for broken last line */
  536.         str[count] = 0;
  537.         for ( j = count - 1; str[j] != NL && j >= 0; )
  538.             j--;
  539.         if ( j < 0 ) {            /* break up long line */
  540.             str[count] = NL;
  541.             str[++count] = EOS;
  542.             strend = str + count;
  543.             linetemp[0] = EOS;
  544.             nleftover = 0;
  545.         }
  546.         else {                /* save partial line */
  547.             strend = str + j;
  548.             nleftover = count - j - 1;
  549.             strncpy ( linetemp, str + j + 1, nleftover );
  550.         }
  551.         k = str + patlen - 1;
  552.  
  553.         for ( ; ; ) {
  554.             /*
  555.                 for a large class of patterns, upwards of 80% of 
  556.                 match time is spent on the next line.  
  557.                 we beat existing microcode (vax 'matchc') this way.
  558.             */
  559. #ifndef V7
  560.             while ( (k += delta0[*(unsigned char *)k]) < strend )
  561.                 ;    
  562. #else
  563.             while ( (k += delta0[*(char *)k & 0377]) < strend )
  564.                 ;
  565. #endif
  566.             if ( k < (str + LARGE) )
  567.                 break;
  568.             k -= LARGE;
  569.  
  570.             j = patlen - 1;
  571.             s = k - 1;
  572.             while ( cmap[*s--] == pattern[--j] )
  573.                 ;
  574.             /*
  575.                 delta-less shortcut for literati, but 
  576.                 short shrift for genetic engineers.
  577.             */
  578.             if ( j >= 0 )
  579.                 k++;
  580.             else {            /* submatch */
  581.                 t = k;
  582.                 s = k - patlen + 1;
  583.                 do 
  584.                     ;
  585.                 while ( *s != NL && --s >= str ); 
  586.                 k = s + 1;    /* at line start */
  587.  
  588.                 if ( boyflag ) {
  589.                     if ( (k = gotamatch ( file, k )) == NULL )
  590.                         return;
  591.                 }
  592.                 else if ( !rxflag ) {    /* fob off to egrep */
  593.                     do
  594.                         putc ( *k, egout );
  595.                     while ( *k++ != NL );
  596.                 }
  597.                 else {                /* regexec() wants EOS */
  598.                     s = t;
  599.                     do
  600.                         ;
  601.                     while ( *s++ != NL );
  602.                     *--s = EOS;
  603.  
  604.                     if ( regexec ( rspencer, ((iflag) ? fold ( k ) : k) ) == 1 ) {
  605.                         *s = NL;
  606.                         if ( gotamatch ( file, k ) == NULL )
  607.                             return;
  608.                     }
  609.                     *s = NL;
  610.                     k = s + 1;
  611.                 }
  612.                 if ( k >= strend )
  613.                     break;
  614.             }
  615.         }
  616.         strncpy ( str, linetemp, nleftover );
  617.     }
  618.     if ( cflag && (boyflag || rxflag) ) {
  619.         if ( nfile > 1 )
  620.             printf ( "%s:", file );
  621.         printf ( "%ld\n", nmatch );
  622.     }
  623. }
  624.  
  625. FILE *
  626. mcilroy ( file )    /* open a pipe to old 'egrep' for long files, */
  627.     char *file;    /* ... where regexp() might be inefficient */
  628. {
  629. #ifdef BSD
  630.     int iflagsave = 0;
  631.     char *patsave;
  632.  
  633.     if ( iflag ) {    
  634.         iflagsave = 1;
  635.         iflag = 0;
  636.         patsave = pattern;
  637.         pattern = sys5fold ( pattern );        /* uncripple -i */
  638.     }
  639. #endif
  640.     /*
  641.         -l via -c is sneaky, but we're short a good prwopen() 
  642.     */
  643.     if ( lflag && !cflag )
  644.         sprintf ( grepcmd, "%s -c %s '%s' | sed -n '/^0$/!s|.*|%s|p'",
  645.                         EGREP, (iflag ? "-i" : " "), pattern, file );
  646.     else if ( nfile <= 1 )
  647.         sprintf ( grepcmd, "%s %s %s '%s'", EGREP,
  648.                     (cflag ? "-c" : " "), (iflag ? "-i" : " "), pattern );
  649.     else
  650.         sprintf ( grepcmd, "%s %s %s '%s' | sed -n 's|^|%s:|p'", EGREP,
  651.                     (cflag ? "-c" : " "), (iflag ? "-i" : " "), pattern, file );
  652.     /*
  653.         we thank mr. thompson for an especial ndfa simulation.
  654.         (consult cacm, june 1968, or aho et. al., design & analysis ...,
  655.         algorithm 9.1).
  656.     */
  657. #ifdef BSD
  658.     if ( iflagsave ) {
  659.         iflag = 1;
  660.         pattern = patsave;
  661.     }
  662. #endif
  663.     return ( popen ( grepcmd, "w" ) );
  664. }
  665.  
  666. gosper ( pattern )        /* compute "boyer-moore" delta table */
  667.     char *pattern;        /* ... HAKMEM lives ... */
  668. {
  669.     register int j, patlen;
  670.     /*
  671.         for multibyte characters (e.g. kanji), there are ways.
  672.         extrapolating 256 to 64K may be unwise, in favor of more
  673.         dynamics within boyermoore() itself. 
  674.     */
  675.     patlen = strlen ( pattern );
  676.  
  677.     for ( j = 0; j < 256; j++ ) {
  678.         delta0[j] = patlen;
  679.         cmap[j] = (char) j;    /* could be done at compile time */
  680.     }
  681.     for ( j = 0; j < patlen - 1; j++ )
  682.         delta0[pattern[j]] = patlen - j - 1;
  683.     delta0[pattern[patlen - 1]] = LARGE;
  684.  
  685.     if ( iflag ) {
  686.         for ( j = 0; j < patlen - 1; j++ )
  687.             if ( islower ( (int) pattern[j] ) )
  688.                 delta0[toupper ((int) pattern[j])] = patlen - j - 1;
  689.         if ( islower ( (int) pattern[patlen - 1] ) )
  690.             delta0[toupper ((int) pattern[patlen - 1])] = LARGE;
  691.         for ( j = 'A'; j <= 'Z'; j++ )
  692.             cmap[j] = (char) tolower ( (int) j );
  693.     }
  694. }
  695.  
  696. char *
  697. gotamatch ( file, s )        /* print, count, or stop on full match */
  698.     register char *file, *s;
  699. {
  700.     nsuccess = 1;
  701.     if ( cflag ) {        /* -c overrides -l, for some reason */
  702.         nmatch++;
  703.         do
  704.             ;
  705.         while ( *s++ != NL );
  706.     }
  707.     else if ( lflag ) {
  708.         puts ( file );
  709.         return ( NULL );
  710.     }
  711.     else {
  712.         if ( nfile > 1 )
  713.             printf ( "%s:", file );
  714.         do
  715.             putchar ( *s );
  716.         while ( *s++ != NL );
  717.     }
  718.     return ( (hflag && !cflag) ? NULL : s );
  719. }
  720.  
  721.  
  722. char *
  723. fold ( line )
  724.     char *line;
  725. {
  726.     static char fline[BUFSIZE];
  727.     register char *s, *t = fline;
  728.  
  729.     for ( s = line; *s != EOS; s++ )
  730.         *t++ = (isupper ((int) *s) ? (char) tolower ((int) *s) : *s );
  731.     *t = EOS;
  732.     return ( fline );
  733. }
  734.     
  735. #ifdef BSD
  736. char *
  737. sys5fold ( line )    /* a workaround kludge for the old alma mater, e.g. */
  738.     char *line;    /* ... "ZIP.*PY" becomes "[zZ][iI][pP].*[pP][yY]" */
  739. {
  740.     register char *p, *s;
  741.     static char pline[BUFSIZE];
  742.     char c, stencil[5];
  743.     int bdanger = 0;
  744.  
  745.     pline[0] = EOS;
  746.     for ( s = line; *s != EOS; s++ ) {
  747.         if ( *s == '[' )
  748.             bdanger = 1;
  749.         if ( bdanger == 1 && *s == ']' )
  750.             bdanger = 0;
  751.         if ( isalpha ( (int) *s ) ) {
  752.             c = ( (islower ( *s )) ? (char) toupper ( (int) *s ) :
  753.                          (char) tolower ( (int) *s ) );
  754.             sprintf ( stencil, ((bdanger) ? "%c%c" : "[%c%c]"), *s, c ); 
  755.         }
  756.         else {
  757.             stencil[0] = *s;
  758.             stencil[1] = EOS;
  759.         }
  760.         strcat ( pline, stencil );
  761.     }
  762.     *s = EOS;
  763.     return ( pline );
  764. }
  765. #endif
  766.  
  767. oops ( message ) 
  768.     char *message;
  769. {
  770.     fprintf ( stderr, "%s\n", message );
  771.     exit ( 2 );
  772. }
  773. SHAR_EOF
  774. if test 11219 -ne "`wc -c < 'egrep.c'`"
  775. then
  776.     echo shar: error transmitting "'egrep.c'" '(should have been 11219 characters)'
  777. fi
  778. fi
  779. echo shar: extracting "'compat-sys5.c'" '(2645 characters)'
  780. if test -f 'compat-sys5.c'
  781. then
  782.     echo shar: will not over-write existing file "'compat-sys5.c'"
  783. else
  784. cat << \SHAR_EOF > 'compat-sys5.c'
  785. /*
  786.  * regcomp(), regexec(), and xread() were posted to mod.sources by
  787.  * henry spencer, and are too large to be included here.
  788.  *
  789.  * This file contains strcspn, strchr, strpbrk, and getopt.
  790.  */
  791.  
  792. #include <stdio.h>
  793. /*
  794.  * strcspn - find length of initial segment of s1 consisting entirely
  795.  * of characters not from s2
  796.  */
  797.  
  798. int strcspn(s1, s2)
  799. char *s1;
  800. char *s2;
  801. {
  802.     register char *scan1;
  803.     register char *scan2;
  804.     register int count;
  805.  
  806.     count = 0;
  807.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  808.         for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  809.             if (*scan1 == *scan2++)
  810.                 return(count);
  811.         count++;
  812.     }
  813.     return(count);
  814. }
  815.  
  816. char *strchr(a, b)
  817. char *a, b;
  818.     {
  819.     char *index();
  820.     return (index(a, b));
  821.     }
  822.  
  823. /* strpbrk - Returns a pointer to the first character of source that is any
  824.  *  of the specified keys, or NULL if none of the keys are present
  825.  *  in the source string.
  826.  */
  827. char *strpbrk(source, keys)
  828. char *source, *keys;
  829. {
  830.         register int loc = 0, key_index = 0;
  831.  
  832.         while (source[loc] != '\0') {
  833.           key_index = 0;
  834.           while (keys[key_index] != '\0')
  835.             if (keys[key_index++] == source[loc])
  836.               return((char *) (source + loc));
  837.           loc++;
  838.         }
  839.         
  840.         return(NULL);
  841. }
  842.  
  843.  
  844. /*
  845.  * getopt - get option letter from argument vector
  846.  */
  847. int    opterr = 1,        /* useless, never set or used */
  848.     optind = 1,        /* index into parent argv vector */
  849.     optopt;            /* character checked for validity */
  850. char    *optarg;        /* argument associated with option */
  851.  
  852. #define BADCH    (int)'?'
  853. #define EMSG    ""
  854. #define tell(s)    fputs(*nargv,stderr);fputs(s,stderr); \
  855.         fputc(optopt,stderr);fputc('\n',stderr);return(BADCH);
  856.  
  857. getopt(nargc,nargv,ostr)
  858. int    nargc;
  859. char    **nargv,
  860.     *ostr;
  861. {
  862.     static char    *place = EMSG;    /* option letter processing */
  863.     register char    *oli;        /* option letter list index */
  864.     char    *index();
  865.  
  866.     if(!*place) {            /* update scanning pointer */
  867.         if(optind >= nargc || *(place = nargv[optind]) != '-' || !*++place) return(EOF);
  868.         if (*place == '-') {    /* found "--" */
  869.             ++optind;
  870.             return(EOF);
  871.         }
  872.     }                /* option letter okay? */
  873.     if ((optopt = (int)*place++) == (int)':' || !(oli = index(ostr,optopt))) {
  874.         if(!*place) ++optind;
  875.         tell(": illegal option -- ");
  876.     }
  877.     if (*++oli != ':') {        /* don't need argument */
  878.         optarg = NULL;
  879.         if (!*place) ++optind;
  880.     }
  881.     else {                /* need an argument */
  882.         if (*place) optarg = place;    /* no white space */
  883.         else if (nargc <= ++optind) {    /* no arg */
  884.             place = EMSG;
  885.             tell(": option requires an argument -- ");
  886.         }
  887.          else optarg = nargv[optind];    /* white space */
  888.         place = EMSG;
  889.         ++optind;
  890.     }
  891.     return(optopt);            /* dump back option letter */
  892. }
  893.  
  894. SHAR_EOF
  895. if test 2645 -ne "`wc -c < 'compat-sys5.c'`"
  896. then
  897.     echo shar: error transmitting "'compat-sys5.c'" '(should have been 2645 characters)'
  898. fi
  899. fi
  900. exit 0
  901. #    End of shell archive
  902.